package io.github.consoles.dsa;

/**
 * Created by yiihua-013 on 17/6/11.
 */
public class ArrayGeneralizedQueue<Item> {

    private static final int DEFAULT_CAPACITY = 2;

    private int    size;
    private Item[] data;

    public ArrayGeneralizedQueue() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayGeneralizedQueue(int cap) {
        data = (Item[]) new Object[cap];
    }

    private void resize(int newSize) {
        Item[] tmp = (Item[]) new Object[newSize];
        for (int i = 0; i < size; i++) tmp[i] = data[i];
        data = tmp;
    }

    void insert(Item item) {
        if (data.length == size) resize(2 * size);
        data[size++] = item;
    }

    boolean isEmpty() {
        return size == 0;
    }

    Item delete(int k) {
        if (k < 1 || k > size) throw new ArrayIndexOutOfBoundsException("越界");
        Item ret = data[k - 1];
        for (int i = k - 1; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;
        if (data.length / 4 == size) resize(size);
        return ret;
    }

}
